home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_02 / 1102090a < prev    next >
Text File  |  1992-12-06  |  2KB  |  83 lines
  1. /*
  2.  *
  3.  * Bose-Nelson algorithm for generating sorting
  4.  * networks.  Calling bose(n) generates a network
  5.  * to sort n items.  See R. C. Bose & R. J. Nelson,
  6.  * "A Sorting Problem", JACM Vol. 9, Pp. 282-296.
  7.  */
  8.  
  9. bose(n)
  10. int n;
  11. {
  12.     Pstar(1, n); /* sort the sequence {X1,...,Xn} */
  13. }
  14.  
  15. P(i, j)
  16. int i, j;
  17. {
  18.     printf("swap(%d, %d);\n", i, j);
  19. }
  20.  
  21. Pstar(i, m)
  22. int i;  /* value of first element in sequence */
  23. int m;  /* length of sequence */
  24. {
  25.     int a;
  26.  
  27.     if(m > 1)
  28.     {
  29.         /*
  30.          * Partition into 2 shorter sequences,
  31.          * generate a sorting method for each,
  32.          * and merge the two sub-networks.
  33.          */
  34.         a = m/2;
  35.         Pstar(i, a);
  36.         Pstar((i + a), (m - a));
  37.         Pbracket(i, a, (i + a), (m - a));
  38.     }
  39. }
  40.  
  41. Pbracket(i, x, j, y)
  42. int i;  /* value of first element in sequence 1 */
  43. int x;  /* length of sequence 1 */
  44. int j;  /* value of first element in sequence 2 */
  45. int y;  /* length of sequence 2 */
  46. {
  47.     int a, b;
  48.  
  49.     if(x == 1 && y == 1)
  50.         P(i, j); /* 1 comparison sorts 2 items */
  51.     else if(x == 1 && y == 2)
  52.     {
  53.         /*
  54.          * 2 comparisons inserts an item into an
  55.          * already sorted sequence of length 2.
  56.          */
  57.         P(i, (j + 1));
  58.         P(i, j);
  59.     }
  60.     else if(x == 2 && y == 1)
  61.     {
  62.         /* As above, but inserting j */
  63.         P(i, j);
  64.         P((i + 1), j);
  65.     }
  66.     else
  67.     {
  68.         /*
  69.          * Recurse on shorter sequences, attempting
  70.          * to make the length of one subsequence odd
  71.          * and the length of the other even.  If we
  72.          * can do this, we eventually merge the two.
  73.          */
  74.         a = x/2;
  75.         b = (x & 1) ? (y/2) : ((y + 1)/2);
  76.         Pbracket(i, a, j, b);
  77.         Pbracket((i + a), (x - a), (j + b), (y - b));
  78.         Pbracket((i + a), (x - a), j, b);
  79.     }
  80. }
  81.  
  82.  
  83.